package cn.edu.leetcode.排序;

import java.lang.reflect.Array;
import java.util.Arrays;

public class 快速排序 {

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int start, int end) {
        if (start >= end) return;
        int start1 = start, end1 = end;
        int x = array[start];
        while (start1 < end1) {
            while (x < array[end1] && start1 < end1) end1--;
            if (start1 < end1) array[start1] = array[end1];
            while (array[start1] < x && start1 < end1) start1++;
            if (start1 < end1) array[end1] = array[start1];
        }
        array[start1] = x;

        quickSort(array, start, start1 - 1);
        quickSort(array, start1 + 1, end);

    }

    public static void main(String[] args) {
        int[] array = {1, 3, 2, 4, 8, 5, 6, 7, 9};
        quickSort(array);

        System.out.println(Arrays.toString(array));
    }
}
